package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/maximum-depth-of-binary-tree/">二叉树的最大深度 [简单]</a>
 * 给定一个二叉树，找出最大深度
 *
 * @author zhenzicheng
 * @date 2022-06-06 11:56
 */
public class MaximumDepthOfBinaryTree_104 {

  /**
   * 递归
   */
  // public int maxDepth(TreeNode root) {
  //   if (root == null) {
  //     return 0;
  //   } else {
  //     return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
  //   }
  // }

  /**
   * 迭代
   */
  public int maxDepth(TreeNode root) {
    Queue<TreeNode> q = new ArrayDeque<>();
    if (root == null) {
      return 0;
    }
    q.offer(root);

    TreeNode cur;
    int depth = 0; // 深度
    while (!q.isEmpty()) {
      int size = q.size(); // 每一次有几个子节点就遍历几次

      for (; size > 0; size--) {
        cur = q.poll();
        assert cur != null;
        if (cur.left != null) { // 保存不为空的元素
          q.offer(cur.left);
        }
        if (cur.right != null) {
          q.offer(cur.right);
        }
      }
      depth++;
    }
    return depth;
  }


}
